/*
Problem Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),
现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,
一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.

注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample Input
banana
band
bee
absolute
acm

ba
b
band
abc
Sample Output
2
3
1
0
 */
package com.yuan.algorithms.team20150724;

import java.util.Scanner;

class Trie {
	private int SIZE = 26;//字典树的大小
	private TrieNode root;//根节点

	public Trie() {
		root = new TrieNode();
	}

	private class TrieNode {
		private int num;//当前节点字符出现的次数
		private TrieNode[] son;//保存所有子节点的数组
		private boolean isEnd;//是否为叶子节点（最后一个节点），每个叶子节点代表一个字符串
		private char val;//字符的值

		public TrieNode() { //初始化节点
			num = 1;
			son = new TrieNode[SIZE];
			isEnd = false;
		}
	}

	/**
	 * 向字典树中插入单词
	 * 
	 * @param str
	 */
	public void insert(String str) {
		if (str == null || str.length() == 0) {
			return;
		}
		TrieNode node = root;
		char[] data = str.toCharArray();
		for (int i = 0, len = str.length(); i < len; i++) {
			int index = data[i] - 'a';
			if (node.son[index] == null) {
				//字典树中当前没有这个字符，新建节点存储这个字符
				node.son[index] = new TrieNode();
				node.son[index].val = data[i];
			} else {
				node.son[index].num++;//字符已存在，则引用数+1
			}
			node = node.son[index];// 延伸树的深度存储下一个值
		}
		node.isEnd = true;// 标记最后一个子树
	}

	/**
	 * 查询以当前字符串为前缀的单词数量
	 * 
	 * @param prefix
	 * @return
	 */
	public int countPrefix(String prefix) {
		if (prefix == null || prefix.length() == 0) {
			return -1;
		}
		TrieNode node = root;
		char[] data = prefix.toCharArray();
		for (int i = 0, len = prefix.length(); i < len; i++) {
			int index = data[i] - 'a';
			if (node.son[index] == null) {
				//没有找到目标字符的索引对象，即目标不存在字典树中
				return 0;
			} else {
				node = node.son[index];// 沿着树的深度向下查找
			}
		}
		return node.num;//返回字符的引用数即前缀数
	}

	/**
	 * 查找字典树中是否有目标字符串完全匹配的结果
	 * 
	 * @param target
	 * @return
	 */
	public boolean has(String target) {
		if (target == null || target.length() == 0) {
			return false;
		}
		TrieNode node = root;
		char[] data = target.toCharArray();
		for (int i = 0, len = data.length; i < len; i++) {
			int index = data[i] - 'a';
			if (node.son[index] == null) {
				//没有索引，字符串不存在
				return false;
			} else {
				node = node.son[index];//更新节点，向下索引
			}
		}
		return node.isEnd;//字符串匹配完成，若是最后一个节点则代表字符串存在
	}

	public TrieNode getRoot() {
		return this.root;
	}
}

public class 字典树_统计难题 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int mark = 0;
		Trie trie = new Trie();
		while (sc.hasNext()) {
			String str = sc.nextLine();
			if (str.length() == 0) {
				mark = 1;
				continue;
			}
			if (mark == 0) {
				trie.insert(str);
			} else {
				System.out.println(trie.countPrefix(str));
			}
		}
	}

}
